package leetcode每日一题;

import java.util.Arrays;
import java.util.Comparator;


/**
 * 1. 问题描述
 *  给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
 *  注意:
 *      可以认为区间的终点总是大于它的起点。
 *      区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
 *
 * 2. 算法分析
 *     难点1：转化题目的求解 为最大互不相交的自区间的数量
 *     难点2：如何求出区间数组中的最大互不相交的自区间的数量
 *
 * 3. 代码实现
 *
 */

/**
 * [1,3] [2,5] [3,4] [5,7]
 *
 * 如果按照右边界从小到大排序，则左边界越小，留出的空白区间越多
 * 如果按照左边界从小到大排序，则右边界越小，留出的空白区间越多
 *
 *
 *
 *
 */
@SuppressWarnings("all")
public class 无重叠区间 {
    public static void main(String[] args) {
        int[][] arr = new int[2][2];
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return 0;
            }
        });
    }

    /**
     * 分析算法实现：
     *       首先我们有n个区间，假设为[ai,bi]  1 <= i <= n,并且假设 a1 <= a2 <= .... <= an
     *        (否则我们对其排序之后重现设置边界占位符)  maxi 表示前i个区间的最大互不相交数量
     *        当我们取出第1个区间的时候，此时最大不相交的区间个数为1 max1 = 1
     *         当我们取出第2个区间的时候，此时我们需要将当前区间和之前所有的区间进行比较
     *         此时我们只有第一个区间，如果第2个区间的左边界大于等于第1个边界的右边界时，此时
     *         两个区间不相交 max2 = 2
     *       否则两个区间相交，则此时 max2 = 1
     *         ...
     *         当我们取出第i个区间的时候，将第i个区间和前i-1个区间进行比较，比较方式如下：
     *         扫描前i-1个区间，假设当前扫描到了第k个区间 [ak,bk]
     *            1. 如果相交 不变
     *            2. 如果不相交 ，如果和当前第k个区间不相交，则将第i个区间添加到前k个区间的互不相交的区间中也是互不相交的
     *               此时maxi = maxk+1
     *
     *  动态规划的算法时间复杂度比较高为O(n^2),下面给出贪心算法的优化，将时间复杂度降低为O(logn)
     * @param intervals
     * @return
     */
    public static int eraseOverlapIntervals1(int[][] intervals) {
        int len = intervals.length;
        if(len == 0 || len == 1) {return 0;}
        // 升序排列区间的左边界，下面的算法是建立在这个基础之上的
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        int[] dp = new int[len]; // dp[i]表示前i个区间中的互不相交区间的最大数量
        // 由于每个区间自身不交，所以dp的初始化为每个位置至少为1
        Arrays.fill(dp,1); // 初始化dp数组
        for(int i = 1; i < len; i++) {
            // 判断当前第i个区间和前i-1个区间之间的关系
            for(int j = 0; j < i; j++) {
                // 如果不相交
                if(intervals[j][1] <= intervals[i][0]) {
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
            }
        }
        return len - Arrays.stream(dp).max().getAsInt();
    }

    /**
     * 贪心算法求解
     * @param intervals
     * @return
     */
    public static int eraseOverlapIntervals2(int[][] intervals) {


        return -1;
    }
}
